Forward error correction (FEC) is often incorporated into a data stream in order to decrease the bit error rate. FEC adds additional information to the data stream to detect and correct any errors that are caused by the transmission system. The additional information is added to each message in a systematic way so that the resultant code words have a one-to-one relation to the messages. For every valid codeword there is one and only one message. For example, for an 8-bit message, one bit of additional information is added in the form of an even parity bit. The message (1 0 1 0 1 0 0 0) becomes the codeword (1 0 1 0 1 0 0 0 1). Therefore, the codeword (0 1 1 0 1 0 0 0 0) is not a valid codeword, even though it is 9 bits long just like the other codeword. In this example, the resultant codeword supports 29 possible bit patterns, but only 28 of those patterns are valid.
Algorithms used for FEC include convolutional codes, Hamming codes, and BCH (Bose-Chaudhuri-Hocquenghem) codes. BCH codes form a large class of powerful random error-correcting cyclic codes, and have the advantage of being robust and very efficient in terms of the relatively low number of check bits required. Reed Solomon codes are an example of a class of BCH codes. BCH codes are specified with three primary parameters, n, k, and t, where n=block length (the length of the message bits plus the additional check bits), k=message length (the number of data bits included in a check block), and t=correctable errors (the number of errors per block which the code can correct).
Galois field or finite field mathematics is the mathematical foundation for BCH-based forward error correction. A Galois field is a type of field extension obtained from considering the coefficients and roots of a given polynomial (also known as the root field). The generator polynomial for a t-error correcting BCH code is specified in terms of its roots from the Galois field GF(2m). If α represents the primitive symbol in GF(2m), then the generator polynomial g(x) for a t-error correcting BCH code of length 2m−1 is the lowest-degree polynomial which has α, α2, α3, . . . α2t as its roots, i.e., g(αi)=0 for 1≦i≦2t. It can be shown from the foregoing that g(x) must be the least common multiple (LCM) of φ1(x), φ3(x), . . . , φ2t−1(x), where φi(x) is the minimal polynomial of αi.
Decoding of BCH codes likewise requires computations using Galois field arithmetic. Galois field arithmetic can be implemented (in either hardware or software) more easily than ordinary arithmetic because there are no carry operations; however, error decoders can nevertheless require a significant amount of logic to implement.
The first step in decoding a t-error correction BCH code is to compute the 2t syndrome components S1, S2, . . . , S2t. For a hardware implementation, these syndrome components may be computed with feedback registers that act as a multiply-accumulator (MAC). Since the generator polynomial is a product of, at most, t minimal polynomials, it follows that, at most, t feedback shift registers (each consisting of at most m stages) are needed to form the 2t syndrome components, and it takes n clock cycles to complete those computations. It is also necessary to find the error-location polynomial that involves roughly 2t2 additions and 2t2 multiplications. Finally, it is necessary to correct the error(s) which, in the worst case (for a hardware implementation), requires t multipliers shifted n times.
Accordingly, circuits that implement BCH codes are typically either quite complex, or require many operations. For example, the BCH-3 iterative algorithm requires up to five separate steps, with each step involving a varying number of computations, and any hardware implementation of BCH-3 must support the maximum possible number of steps/computations. Implementation of the calculations in electronic circuits can be accomplished with serial based hardware. However, performing calculations serially can take multiple clock cycles for operations to complete. Usage of serial techniques to perform many Galois field operations, including multiplication and division, may not meet system performance goals and may require the use of parallel techniques. The design and implementation of parallel circuitry to perform the calculations is often tedious and error prone. As the above examples show, improved techniques for implementing BCH circuits are desirable.